﻿using System;

namespace Domain
{
    public class InterpolationSearch
    {
        public int FindElement(int[] array, int toFind)
        {
            if (array.Length == 0)
            {
                throw new Exception();
            }

            int low = 0;
            int high = array.Length - 1;

            while ((array[low] < toFind) && (array[high] > toFind))
            {
                int mid = low + ((toFind - array[low])*(high - low))/(array[high] - array[low]);

                if (array[mid] < toFind)
                    low = mid + 1;
                else if (array[mid] > toFind)
                    high = mid - 1;
                else
                    return mid;
            }

            if (array[low] == toFind)
                return low;
            if (array[high] == toFind)
                return high;
            return -1;
        }
    }
}
